#include<iostream>
#include<map>
#include<cstring>
#include<stdio.h>
#include<cstdlib>

using namespace std;

map<int,int> m;
map<int,int>::const_iterator it;

inline int serve_highest_pri()
{
    if( m.size()==0 )    
        return 0;
    
    it = m.end();
    it--;
    
    int res = it->second;
    m.erase(it->first);
    return res;
}

inline int serve_lowest_pri()
{
    if( m.size()==0 )   
        return 0;
    
    it = m.begin();
    int res = it->second; 
    m.erase(it->first);
    return res;
}

int main()
{
    int k,p,n,res;
    while( scanf("%d",&n) )    
    {
        if(n==0)            
        {
            break;                    
        }
        else if(n==1)
        {
            scanf("%d%d",&k,&p);
            m[p] = k; 
            continue;       
        }
        else if(n==2)
        {
            res = serve_highest_pri();
            if(res==0)
            {
                cout<<0<<endl;                 
            }
            else
            {
                cout<<res<<endl;
            }
            continue;
        }
        else
        {
            res = serve_lowest_pri();
            if(res==0)
            {
                cout<<0<<endl;                 
            }
            else
            {
                cout<<res<<endl;
            }
        }
    }//while
    
    system("pause");
    return 0;
} 
